package com.acwing.partition3;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/11/27 16:21
 */
public class AC283石子合并 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int[] stones = new int[n];
        s = reader.readLine().split(" ");
        for (int i = 0; i < s.length; i++) {
            stones[i] = Integer.parseInt(s[i]);
        }
//        writer.write(dynamicProgramming(stones) + "\n");
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + stones[i - 1];
        writer.write(memoization(prefix, new int[n][n], 0, n - 1) + "\n");
        writer.flush();
    }

    private static int memoization(int[] prefix, int[][] memo, int i, int j) {
        if (i == j) return 0;
        if (memo[i][j] != 0) return memo[i][j];
        memo[i][j] = 0x3f3f3f3f;
        for (int k = i; k < j; k++) {
            int res = memoization(prefix, memo, i, k) + memoization(prefix, memo, k + 1, j);
            memo[i][j] = Math.min(memo[i][j], res + prefix[j + 1] - prefix[i]);
        }
        return memo[i][j];
    }

    private static int dynamicProgramming(int[] stones) {
        int n = stones.length;
        //区间dp，dp[i][j]表示合并stones[i]和stones[j]需要的最小体力
        int[][] dp = new int[n][n];
        int[] prefix = new int[n + 1];
        //使用前缀和进行预处理，方便计算合并任意连续堆需要的体力值
        for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + stones[i - 1];
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i + length - 1 < n; i++) {
                int j = i + length - 1;
                dp[i][j] = 0x3f3f3f3f;
                //枚举区间[i, j]的分割线k
                for (int k = i; k < j; k++) {
                    //dp[i][k] + dp[k + 1][j]：除了最后一次合并的最小代价；prefix[j + 1] - prefix[i]：最后一步合并的代价
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefix[j + 1] - prefix[i]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
